package Test.offer;


import basic.study.wantOffer.chapter3.Problem36;

/**
 * @ClassName P36
 * @Description
 * @Company inspur
 * @Author Kevin
 * @Date 2020/8/1 19:08
 * @Version 1.0
 */
public class P36 {

    BinaryTreeNode Convert(BinaryTreeNode root) {
        if (root == null) return root;
        BinaryTreeNode last = null;
        last = Convert(root, last);

        while (last != null && last.left != null) {
            last = last.left;
        }
        return last;
    }

    private BinaryTreeNode Convert(BinaryTreeNode root, BinaryTreeNode last) {
        if (root == null) return null;
        //如果有左子树，先遍历左子树
        if (root.left != null) {
            last = Convert(root.left, last);
        }
        root.left = last;
        if (last != null) {
            last.right = root;
        }
        last = root;
        //如果有右子树
        if (root.right != null) {
            last = Convert(root.right, last);
        }
        return last;
    }


    class BinaryTreeNode {
        private int data;
        private BinaryTreeNode left;
        private BinaryTreeNode right;
    }
}
